Fermat の小定理 - Summer498 の頭ん中

Fermat の小定理

素数関連でとにかく出てきまくる重要な定理

出てきすぎて数論における基本的な内容ですらある

拡張版: Euler の定理, Carmichael の定理

Fermat の最終定理が有名すぎて「小」と名前についてしまっている

英語でも Fermat's little theorem と呼ばれる

証明は G. Leibnizによって与えられている

$ p\in\mathbb P,\ a\in\Zとすると

$ a^p\overset p\equiv a

特に、$ \gcd(a,p)=1の時、

$ a^{p-1}\overset p\equiv1

ちなみに

$ a^{-1}\overset p\equiv a^{p-2}

証明1

補題: $ (m+1)^p\overset p\equiv m^p+1が成立

$ \because(m+1)^p=m^p+\sum_{k=1}^{p-1}\,_pC_km+1

$ \because\,_pC_k=\frac{p!}{(p-k)!k!}\overset p\equiv0

$ pが素数なので約分で消えない

本証明

数学的帰納法により示す

$ a=2の時$ 2^p\overset p\equiv 2が成立

補題に$ m=1を代入すると$ (1+1)^p\overset p\equiv 1^p+1

$ a=kのときの成立($ k^p\overset p\equiv k)を仮定すると

$ (k+1)^p\overset p\equiv k^p+1補題より

$ \overset p\equiv k+1

$ (k+1)^p\overset p\equiv(k+1)

証明2

補題: $ (x+y)^p\overset p\equiv x^p+y^p

証明は証明 1 の補題と同様

$ a^p=[1+(a-1)]^p

$ \overset p\equiv1^p+(a-1)^p

$ \overset p\equiv1^p+[1+(a-2)]^p

$ \overset p\equiv1^p+1^p+(a-2)^p

$ \overset p\equiv\cdots

$ \overset p\equiv a